package com.test.demo;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

/**
 * Created by jl on 2019/7/19 0019
 * 枚举m位二进制所有可能性
 * 1.复杂实现，很耗内存
 * 2.简单递归，优化很多的实现
 */
public class StateSequence {
    public static void main(String[] args) {
//        Thread thread = new Thread(new Runnable() {
//            @Override
//            public void run() {
//                try {
//                    Thread.sleep(15000);
//                } catch (InterruptedException e) {
//                    e.printStackTrace();
//                }
//
//                long startMills = System.currentTimeMillis();
//                enumAll(19);
//                long endMills = System.currentTimeMillis();
//                System.out.println("耗时：" + (endMills - startMills) + "ms");
//            }
//        });
//        thread.setDaemon(true);
//        thread.setName("river");
//        thread.start();
//        try {
//            Thread.sleep(1000000);
//        } catch (InterruptedException e) {
//            e.printStackTrace();
//        }
////        System.out.println(1 << 20);
        short[] a = new short[2];
        optimizeImpl(a, 0);
    }

    private static void enumAll(int cnt) {
        SateSerial sateSerial = initSateSerial(cnt);
        HashMap<Integer, List<SateSerial>> sateSerialMap = new HashMap<>(1024);
        for (int i = 0; i <= cnt; i++) {
            enumWithActiveCnt(i, sateSerial, sateSerialMap);
        }
        // print
        Counter counter = new Counter();
        sateSerialMap.forEach((key, value) -> {
            value.forEach(item ->{
                System.out.println(item.toString());
                counter.count++;
            });
        });
        System.out.println("总个数：" + counter.count);
    }

    private static void enumWithActiveCnt(int activeCnt, SateSerial sateSerial, HashMap<Integer, List<SateSerial>> sateSerialMap) {
        List<SateSerial> sateSerials = new ArrayList<>();
        if (activeCnt == 0) {
            sateSerials.add(sateSerial);
        } else {
            List<SateSerial> curSateSerials = sateSerialMap.get(activeCnt - 1);
            for (int i = 0; i < curSateSerials.size(); i++) {
                List<SateSerial> sateSerial2Add = onePointMove(curSateSerials.get(i).snapshot());
                sateSerials.addAll(sateSerial2Add);
                // 最后n-1个为1的时候只用move一遍
                if (sateSerial.states.size() == activeCnt) {
                    break;
                }
            }
        }
        sateSerialMap.put(activeCnt, sateSerials);
    }

    private static List<SateSerial> onePointMove(SateSerial sateSerial) {
        List<SateSerial> sateSerials = new ArrayList<>();
        List<State> states = sateSerial.getStates();
        int prevIndex = -1;
        int start = sateSerial.searchStartPos();
        for (int i = start; i < states.size(); i++) {
            if (states.get(i).v == 0) {
                states.get(i).v = 1;
                if (prevIndex > -1) {
                    states.get(prevIndex).v = 0;
                }
                sateSerials.add(sateSerial.snapshot());
                prevIndex = i;
            }
        }
        return sateSerials;
    }

    private static SateSerial initSateSerial(int cnt) {
        SateSerial sateSerial = new SateSerial();
        List<State> states = new ArrayList<>();
        for (int i = 0; i < cnt; i++) {
            states.add(new State((short) 0));
        }
        sateSerial.setStates(states);
        return sateSerial;
    }

    private static class SateSerial {
        private List<State> states;

        public List<State> getStates() {
            return states;
        }

        public void setStates(List<State> states) {
            this.states = states;
        }

        @Override
        public String toString() {
            StringBuilder stringBuilder = new StringBuilder();
            states.forEach(state -> stringBuilder.append(state.v));
            return stringBuilder.toString();
        }

        public SateSerial snapshot() {
            SateSerial sateSerial = new SateSerial();
            List<State> newStates = new ArrayList<>();
            states.forEach(state -> newStates.add(new State(state.v)));
            sateSerial.setStates(newStates);
            return sateSerial;
        }

        public int searchStartPos() {
            for (int i = states.size() - 1; i >= 0; i--) {
                if (states.get(i).v == 1) {
                    return i;
                }
            }
            return 0;
        }
    }

    private static class State {
        short v;

        public State(short v) {
            this.v = v;
        }
    }

    private static class Counter {
        int count = 0;
    }

    /**
     * 优化后的实现版本
     */
    private static void optimizeImpl(short[] a, int n) {
        if (n < a.length) {
            a[n] = 0;
            optimizeImpl(a, n + 1);
            a[n] = 1;
            optimizeImpl(a, n + 1);
        } else {
            StringBuilder sb = new StringBuilder();
            for (int i = 0; i < a.length; i++) {
                sb.append(a[i]);
            }
            System.out.println(sb.toString());
        }
    }
}
